Givens Rotation

In numerical linear algebra, a Givens rotation is a rotation in the plane spanned by two coordinates axes. Givens rotations are named after Wallace Givens, who introduced them to numerical analysts in the 1950s while he was working at Argonne National Laboratory.

Matrix representation

A Givens rotation is represented by a matrix of the form

:$G(i, j, \theta) = \begin 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & c & \cdots & -s & \cdots & 0 \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & s & \cdots & c & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end,$

where and appear at the intersections th and th rows and columns. That is, for fixed , the non-zero elements of Givens matrix are given by:
:$\begin g_ &= 1 \qquad \text \ k \ne i,\,j\\ g_ &= c \qquad \text \ k = i,\,j\\ g_ & = -g_= -s\\ \end$

The product represents a counterclockwise rotation of the vector in the plane of radians, hence the name Givens rotation.

The main use of Givens rotations in numerical linear algebra is to introduce zeros in vectors or matrices.
This effect can, for example, be employed for computing the QR decomposition of a matrix. One advantage over Householder transformations is that they can easily be parallelised, and another is that often for very sparse matrices they have a lower operation count.

Stable calculation

When a Givens rotation matrix, , multiplies another matrix, , from the left, , only rows and of are affected. Thus we restrict attention to the following counterclockwise problem. Given and , find and such that
:$\begin c & -s \\ s & c \end \begin a \\ b \end = \begin r \\ 0 \end ,$
where $r = \sqrt$ is the length of the vector $(a,b)$.
Explicit calculation of is rarely necessary or desirable. Instead we directly seek and . An obvious solution would be
:$\begin c &\larr a / r \\ s &\larr -b / r. \end$

However, the computation for may overflow or underflow. An alternative formulation avoiding this problem is implemented as the hypot function in many programming languages.

The following Fortran code is a minimalistic implementation of Givens rotation for real numbers. If the input values 'a' or 'b' are frequently zero, the code may be optimized to handle these cases as presente
here

subroutine givens_rotation(a, b, c, s, r)

real a, b, c, s, r
real h, d

if (b.ne.0.0) then
h = hypot(a, b)
d = 1.0 / h
c = abs(a) * d
s = sign(d, a) * b
r = sign(1.0, a) * h
else
c = 1.0
s = 0.0
r = a
end if

return
end

Furthermore, as Edward Anderson discovered in improving LAPACK, a previously overlooked numerical consideration is continuity. To achieve this, we require to be positive. The following MATLAB/GNU Octave code illustrates the algorithm.

function , s, r= givens_rotation(a, b)
if b

0;
c = sign(a);
if (c

0);
c = 1.0; % Unlike other languages, MatLab's sign function returns 0 on input 0.
end;
s = 0;
r = abs(a);
elseif a

0;
c = 0;
s = sign(b);
r = abs(b);
elseif abs(a) > abs(b);
t = b / a;
u = sign(a) * sqrt(1 + t * t);
c = 1 / u;
s = c * t;
r = a * u;
else
t = a / b;
u = sign(b) * sqrt(1 + t * t);
s = 1 / u;
c = s * t;
r = b * u;
end
end

The IEEE 754 copysign(x,y) function, provides a safe and cheap way to copy the sign of y to x. If that is not available, , using the abs and sgn functions, is an alternative as done above.

Triangularization

Given the following Matrix:

:$A_1 = \begin 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end,$

perform two iterations of the Givens rotation (note that the Givens rotation algorithm used here differs slightly from above) to yield an upper triangular matrix in order to compute the QR decomposition.

In order to form the desired matrix, we must zero elements and . We first select element to zero. Using a rotation matrix of:
:$G_ = \begin c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \\ \end.$

We have the following matrix multiplication:
:$\begin G_1 A_1 &= A_2 \\ & = \begin c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \\ \end \begin 6 & 5 & 0 \\ 5 & 1 & 4 \\ 0 & 4 & 3 \\ \end, \end$

where
:$\begin r &= \sqrt \approx 7.8102 \\ c &= 6 / r \approx 0.7682 \\ s &= -5 / r \approx -0.6402. \end$

Plugging in these values for and and performing the matrix multiplication above yields :
:$A_2 \approx \begin 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end$

We now want to zero element to finish off the process. Using the same idea as before, we have a rotation matrix of:
:$G_ = \begin 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end$

We are presented with the following matrix multiplication:
:$\begin G_2 A_2 &= A_3 \\ &\approx \begin 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \\ \end \begin 7.8102 & 4.4813 & 2.5607 \\ 0 & -2.4327 & 3.0729 \\ 0 & 4 & 3 \\ \end, \end$

where
:$\begin r &\approx \sqrt \approx 4.6817 \\ c &\approx -2.4327 / r \approx -0.5196 \\ s &\approx -4 / r \approx -0.8544. \end$
Plugging in these values for and and performing the multiplications gives us :
:$A_3 \approx \begin 7.8102 & 4.4813 & 2.5607 \\ 0 & 4.6817 & 0.9664 \\ 0 & 0 & -4.1843 \\ \end.$

This new matrix is the upper triangular matrix needed to perform an iteration of the QR decomposition. is now formed using the transpose of the rotation matrices in the following manner:

:$Q = G_^T\, G_^T.$

Performing this matrix multiplication yields:
:$Q \approx \begin 0.7682 & 0.3327 & 0.5470 \\ 0.6402 & -0.3992 & -0.6564 \\ 0 & 0.8544 & -0.5196 \\ \end.$

This completes two iterations of the Givens Rotation and calculating the QR decomposition can now be done.

In Clifford algebras

In Clifford algebras and its child structures like geometric algebra rotations are represented by bivectors. Givens rotations are represented by the exterior product of the basis vectors. Given any pair of basis vectors $\mathbf e_i, \mathbf e_j$ Givens rotations bivectors are:

: $B_ = \mathbf e_i \wedge \mathbf e_j.$

Their action on any vector is written:

: $v=e^u e^,$

where

: $e^= \cos(\theta/2)+ \sin(\theta/2) \mathbf e_i \wedge \mathbf e_j.$

Dimension 3

There are three Givens rotations in dimension 3:

:$R_X(\theta) = \begin 1 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta \\ 0 & \sin \theta & \cos \theta \end.$

:$\begin \\ R_Y(\theta) = \begin \cos \theta & 0 & -\sin \theta \\ 0 & 1 & 0 \\ \sin \theta & 0 & \cos \theta \end \end$

:$\begin \\ R_Z(\theta) = \begin \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end \end$

Given that they are endomorphisms they can be composed with each other as many times as desired, keeping in mind that .

These three Givens rotations composed can generate any rotation matrix according to Davenport chained rotations, Davenport's chained rotation theorem. This means that they can transformation (geometry), transform the standard basis of the space to any other frame in the space.

When rotations are performed in the right order, the values of the rotation angles of the final frame will be equal to the Euler angles of the final frame in the corresponding convention. For example, an operator $R = R_Y(\theta_3).R_X(\theta_2).R_Z(\theta_1)$ transforms the basis of the space into a frame with angles roll, pitch and yaw $YPR = (\theta_3,\theta_2,\theta_1)$ in the Tait–Bryan angles, Tait–Bryan convention ''z''-''x''-''y'' (convention in which the line of nodes is perpendicular to ''z'' and ''Y'' axes, also named ''Y''-''X′''-''Z″'').

For the same reason, any rotation matrix in 3D can be decomposed in a product of three of these three-dimensional rotation operator, rotation operators.

The meaning of the composition of two Givens rotations is an operator that transforms vectors first by and then by , being and rotations about one axis of basis of the space. This is similar to the Euler angles#Euler angles as composition of extrinsic rotations, extrinsic rotation equivalence for Euler angles.

Table of composed rotations

The following table shows the three Givens rotations equivalent to the different Euler angles conventions using extrinsic composition (composition of rotations about the basis axes) of Active and passive transformation, active rotations and the right-handed rule for the positive sign of the angles.

The notation has been simplified in such a way that means and means . The subindexes of the angles are the order in which they are applied using ''extrinsic'' composition (1 for intrinsic rotation, 2 for nutation, 3 for precession)

As rotations are applied just in the opposite order of the Euler angles#Table of composed rotations, Euler angles table of rotations, this table is the same but swapping indexes 1 and 3 in the angles associated with the corresponding entry. An entry like ''zxy'' means to apply first the ''y'' rotation, then ''x'', and finally ''z'', in the basis axes.

All the compositions assume the right hand convention for the matrices that are multiplied, yielding the following results.

:

See also

* Jacobi rotation
* Plane of rotation
* Householder transformation
* Davenport rotations

Notes

Citations

References

* . LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, January 31, 2001.
*
* .
*

{{Numerical linear algebra

Articles with example MATLAB/Octave code
Matrices
Numerical linear algebra
Rotation in three dimensions